//给你一个仅由小写英文字母组成的字符串 s 。 
//
// 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字
//符串。 
//
// 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。 
//
// 子字符串 是字符串中的一个连续 非空 字符序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aaaa"
//输出：2
//解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
//可以证明最大长度是 2 。
// 
//
// 示例 2： 
//
// 
//输入：s = "abcdef"
//输出：-1
//解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
// 
//
// 示例 3： 
//
// 
//输入：s = "abcaba"
//输出：1
//解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
//可以证明最大长度是 1 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= s.length <= 50 
// s 仅由小写英文字母组成。 
// 
//
// Related Topics 哈希表 字符串 二分查找 计数 滑动窗口 👍 3 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;

/**
 * @author ldltd
 * @date 2024-05-29 00:14:53
 * @description 2981.找出出现至少三次的最长特殊子字符串 I
 */
public class FindLongestSpecialSubstringThatOccursThriceI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindLongestSpecialSubstringThatOccursThriceI fun=new FindLongestSpecialSubstringThatOccursThriceI();
	 	 Solution solution = fun.new Solution();
		 System.out.println(solution.maximumLength("cccerrrecdcdccedecdcccddeeeddcdcddedccdceeedccecde"));

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximumLength(String s) {
		int n = s.length();
		int l=1,r=n-1;
		int res=-1;
		while (l<r){
			//二分，在每个确定长度内遍历，
			int m=l+r>>1;
			HashMap<String, Integer> map = new HashMap<>();
			boolean flag1=false;
			for (int i = 0; i < n-m+1; i++) {
				boolean flag2=true;
				for (int j = 0; flag2&&(j < m-1); j++) {
					if(s.charAt(j+i)!=s.charAt(i+j+1)){
						//如果不是重复字符，就不计算次数了
						flag2=false;
					}
				}
				if(!flag2)continue;
				String substring = s.substring(i, i + m);
				//统计当前长度重复字符串的长度
				map.merge(substring,1,Integer::sum);
				//如果有一个重复字符串出现的次数大于等于3标记当前解可用
				if((map.get(substring) >=3)){
					flag1=true;
				}
			}
			//如果当前解可用，收缩左边界，保存答案
			if(flag1){
				l=m+1;
				res=Math.max(res,m);
			}else {
				r=m;
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
